package algorthm.systemTraning.unionSearch;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import util.RandomUtil;

import java.security.cert.PolicyNode;
import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
import java.util.stream.IntStream;

/**
 * @className: LAN
 * @Description:
 * @Author: wangyifei
 * @Date: 2024/4/24 16:28
 */
public class LAN {
    /**
     * 在一个机房中，服务器的位置标识在 n*m 的整数矩阵网格中，1 表示单元格上有服务器，0 表示没有。如果两台服务器位于同一行或者同一列中紧邻的位置，则认为它们之间可以组成一个局域网。
     * 请你统计机房中最大的局域网包含的服务器个数。
     * */
    public static void main(String[] args) {
        for(int a = 0 ; a < 100000 ; a++){
            int m = RandomUtil.randIntRange(2 , 5 , 10);
            int n = RandomUtil.randIntRange(2 , 5 , 10);
            int[][] map = new int[m][n];
            for(int i = 0 ; i < m ; i++){
                for(int j = 0 ; j < n ; j++){
                    map[i][j] = (RandomUtil.randBoolean()? 1 : 0);
                }
            }
            long start = System.currentTimeMillis();
            int i1 = maxLANServer(map);
            long p = System.currentTimeMillis();
//            System.out.println("maxLANServer duration: " + (p - start));
            int i2 = maxLANServer2(map);
//            System.out.println("maxLANServer2 duration: " + (System.currentTimeMillis() - start));
            if(i1 != i2){
               System.out.println("Opps , maxLANServer: " + i1 + " , maxLANServer2:" + i2);
                for(int i = 0 ; i < m ; i++){
                    for(int j = 0 ; j < n ; j++){
                        System.out.print(map[i][j] + " ");
                    }
                    System.out.println();
                }
               return ;
            }
        }
    }
    public static int maxLANServer2(int[][] map){
        UnionSet2 us = new UnionSet2();
        us.col = map[0].length ;
        us.row = map.length;
        us.help = new int[us.col * us.row];
        us.parents = new int[us.col * us.row];
        us.sizeSet = new int[us.col * us.row];
        for(int i = 0 ; i < map.length ; i++){
            for(int j = 0 ; j < map[i].length ; j++){
                if(map[i][j] == 1){
                    int index = us.index(i, j);
                    us.parents[index] = index;
                    us.sizeSet[index] = 1 ;
                }
            }
        }
        for(int i = 1 ; i < map[0].length ; i++){
            if(map[0][i-1] == 1 && map[0][i] == 1){
                us.union(0 , i -1 , 0 , i);
            }
        }
        for(int i = 1 ; i < map.length ; i++){
            if(map[i-1][0] == 1 && map[i][0] == 1){
                us.union(i-1 , 0 , i , 0);
            }
        }
        for(int i = 1 ; i < map.length ; i++){
            for(int j = 1 ; j < map[0].length ; j++){
                if(map[i][j-1] == 1 && map[i][j] == 1){
                    us.union(i , j -1 , i , j);
                }
                if(map[i -1][j] == 1 && map[i][j] == 1){
                    us.union(i - 1 , j , i , j);
                }
            }
        }
        int maxSize = 0 ;
        for(int size : us.sizeSet){
            maxSize = Math.max(maxSize , size);
        }
        return maxSize;
    }
    public static class UnionSet2{
        public int[] parents ;
        public int[] sizeSet ;
        public int[] help ;
        public int col ;
        public int row ;
        public void union(int x , int y , int i , int j){
            int xyFather = find(x , y);
            int ijFather = find(i , j);
            if(xyFather != ijFather){
                int big = (sizeSet[xyFather] > sizeSet[ijFather] ? xyFather : ijFather );
                int small = (sizeSet[xyFather] <= sizeSet[ijFather] ? xyFather : ijFather );
                parents[small] = big ;
                sizeSet[big] += sizeSet[small];
                sizeSet[small] = 0 ;
            }
        }
        public int index(int x , int y){
            return x * col + y ;
        }
        public int find(int x , int y){
            int idx = 0 ;
            int cur = index(x , y);
            while(cur != parents[cur]){
                help[idx++] = cur ;
                cur = parents[cur];
            }
            idx--;
            while(idx>=0){
                parents[help[idx]] = cur ;
               idx-- ;
            }
            return cur ;
        }
    }
    public static int maxLANServer(int[][] map){
        int m = map.length;
        int n = map[0].length;
        Point[][] parents = new Point[m][n];
        int[][] size = new int[m][n];
        Point[] help = new Point[ m * n];
        Point[][] points = new Point[m][n] ;
        for(int i = 0 ; i < map.length ; i++){
            for(int j = 0 ; j < map[i].length ; j++){
                points[i][j] = new Point(i , j , map[i][j]);
                if(map[i][j] == 1){
                    parents[i][j] = new Point(i , j , map[i][j]);
                    size[i][j] = 1 ;
                }
            }
        }
        UnionSet us = new UnionSet(points , parents , size , help);
        for(int i = 0 ; i < map.length ; i++){
            int j = 0 ;
            Point pre = null ;
            Point curr = null ;
            for( ; j < map[i].length ; j++){
                curr = points[i][j];
                if(map[i][j] == 1 && null != pre && pre.value == 1){
                    us.union(curr , pre);
                }
                pre = curr ;
            }
        }

        for(int i = 0 ; i < map[0].length ; i++){
            Point pre = null ;
            Point curr = null ;
            for(int j = 0 ; j < map.length; j++){
                curr = points[j][i];
                if(map[j][i] == 1 && pre != null && pre.value == 1){
                    us.union(curr , pre);
                }
                pre = curr ;
            }
        }
        int maxSize = 0 ;
        for (int[] ints : us.size) {
            for(int i : ints){
                maxSize = Math.max(maxSize , i);
            }
        }
        return maxSize;
    }
    public static class UnionSet{
        public Point[][] points ;
        public Point[][] parents ;
        public int[][] size ;
        public Point[] help ;
        public UnionSet(Point[][] ps ,Point[][] p , int[][] s , Point[] h){
            points = ps ;
            parents = p ;
            size = s ;
            help = h ;
        }
        public void union(Point x , Point y){
            Point xPoint = getFather(x);
            Point yPoint = getFather(y);
            if(!xPoint.equals(yPoint)){
                Point big = ( size[xPoint.x][xPoint.y] > size[yPoint.x][yPoint.y] ? xPoint : yPoint);
                Point small =  ( size[xPoint.x][xPoint.y] <= size[yPoint.x][yPoint.y] ? xPoint : yPoint);
                parents[small.x][small.y] = big ;
                size[big.x][big.y] += size[small.x][small.y];
                size[small.x][small.y] = 0 ;
            }
        }
        public Point getFather(Point p){
            int idx = 0 ;
            Point curr = points[p.x][p.y] ;
            while(!(curr.x == parents[curr.x][curr.y].x && parents[curr.x][curr.y].y == curr.y)){
                help[idx++] =  parents[curr.x][curr.y] ;
                curr = parents[curr.x][curr.y];
            }
            idx--;
            while(idx>=0){
                parents[help[idx].x][help[idx].y] = curr ;
                idx--;
            }
            return curr ;
        }
    }
    public static class Point{
        public int x ;
        public int y ;
        public int value ;
        public Point(int x , int y , int v){
            this.x = x ;
            this.y = y ;
            value = v ;
        }
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Point point = (Point) o;
            return x == point.x && y == point.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }
}
